#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "algorithm"

using namespace std;
/*
 * 输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
 *
 * */

vector<string> res;
string temp;
vector<int> used;

void dfs(string &s) {
    if (temp.size() == s.size()) {
        res.push_back(temp);
        return;
    }

    for (int i = 0; i < s.size(); ++i) {
        if (used[i] == 1)
            continue;

        if (i > 0 && s[i] == s[i - 1] && used[i - 1] == 0)
            continue;


        used[i] = 1;
        temp.push_back(s[i]);
        dfs(s);
        temp.pop_back();
        used[i] = 0;
    }


}

vector<string> permutation(string s) {
    sort(s.begin(), s.end());
    used.resize(s.size(), 0);
    dfs(s);
    return res;
}